#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

//class Solution {
//public:
//  
//    vector<vector<int>> generate(int numRows) 
//    {
//        vector<vector<int>> ret;
//        for (int i = 1; i <= numRows; ++i)
//        {
//            vector<int> tmp(i, 1);
//            for (int j = 1; j < i - 1; ++j)
//            {
//                tmp[j] = ret[i - 2][j] + ret[i - 2][j - 1];
//            }
//            ret.push_back(tmp);
//        }
//        return ret;
//    }
//
//};
//int main()
//{
//    vector<vector<int>> v = Solution().generate(5);
//    return 0;
//}


#include<cstring>
#include <queue>

#include<functional>

namespace my
{
    template<class T, class Container = std::vector<T>, class Compare = less<T>>
    class priority_queue
    {
    public:
        priority_queue() = default;
       
        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            InputIterator it = first;
            while (it != last)
            {
                push(*it);
                ++it;
            }
        }

        bool empty() const
        {
            return c.empty();
        }
        size_t size() const
        {
            return c.size();
        }
        const T& top() const
        {
            return c[0];
        }
        void push(const T& x)
        {
            c.push_back(x);
            AdjustUp(size() - 1);
        }
        void pop()
        {
            swap(c[0], c[size() - 1]);
            c.pop_back();
            AdjustDown(0);
        }

    private:
        void AdjustUp(int child)
        {
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (Com(c[parent], c[child]))
                {
                    swap(c[parent], c[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void AdjustDown(int parent)
        {
            int child = 2 * parent + 1;
            if (child + 1 < size() && Com(c[child], c[child + 1]))
                child++;
            while (child < size())
            {
                if (Com(c[parent], c[child]))
                {
                    swap(c[parent], c[child]);
                    parent = child;
                    child = 2 * parent + 1;
                    if (child + 1 < size() && Com(c[child], c[child + 1]))
                        child++;
                }
                else
                    break;
            }
        }

    private:
        Container c;
        Compare Com;
    };
}

//int main()
//{
//    
//    vector<int> v = { 3,5,4,2,9,8 };
//    my::priority_queue<int> pq(v.begin(), v.end());
// /*   pq.push(3);
//    pq.push(5);
//    pq.push(4);
//    pq.push(2);
//    pq.push(9);
//    pq.push(7);
//    pq.push(8);*/
//    pq.pop();
//    pq.empty();
//    pq.size();
//    cout << pq.top() << endl;
//    return 0;
//}
//int main()
//{
//    my::priority_queue<int> pq;
//    pq.push(10);
//    pq.push(20);
//    pq.push(30);
//
//    cout << pq.top() << endl;
//    pq.pop();
//    pq.pop();
//    cout << pq.top() << endl;
//
//    return 0;
//}
#include<cstdlib>
#include<string>
//class Solution {
//public:
//    
//    string multiply(string num1, string num2) 
//    {
//        int a1 = atoi(num1.c_str());
//        int a2 = atoi(num2.c_str());
//
//        long long ret = a1 * a2;
//        string s = to_string(ret);
//
//        return s;
//    }
//};

//class Date
//{
//public:
//    int GetMonthDay(int year, int month)
//    {
//        static int a[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//        if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
//            return a[month] + 1;
//        else
//            return a[month];
//    }
//    Date(int year = 1900, int month = 1, int day = 1)
//        :_year(year)
//        ,_month(month)
//        ,_day(day)
//    {}
//
//    Date(const Date& d)
//        :_year(d._year)
//        ,_month(d._month)
//        ,_day(d._day)
//    {}
//    
//    Date& operator=(const Date& d)
//    {
//        _year = d._year;
//        _month = d._month;
//        _day = d._day;
//        return *this;
//    }
//
//    Date& operator+=(int day)
//    {
//        _day += day;
//        while (_day > GetMonthDay(_year, _month))
//        {
//            _day -= GetMonthDay(_year, _month);
//            if (_month == 12)
//            {
//                _month = 1;
//                ++_year;
//            }
//            else
//            {
//                ++_month;
//            }
//        }
//        return *this;
//    }
//
//    Date operator+(int day)
//    {
//        Date tmp = *this;
//        tmp += day;
//        return tmp;
//    }
//
//    Date& operator-=(int day)
//    {
//        while (day)
//        {
//            if (_day != 1)
//                --_day;
//            else
//            {
//                if (_month != 1)
//                {
//                    --_month;
//                    _day = GetMonthDay(_year, _month);
//                }
//                else
//                {
//                    --_year;
//                    _month = 12;
//                    _day = 31;
//                }
//            }
//            --day;
//        }
//        return *this;
//    }
//    Date operator-(int day)
//    {
//        Date tmp = *this;
//        tmp -= day;
//        return tmp;
//    }
//
//    bool operator==(const Date& d)
//    {
//        if (_year == d._year && _month == d._month && _day == d._day)
//            return true;
//        else
//            return false;
//    }
//
//    friend ostream& operator<<(ostream& out, const Date& d);
//private:
//    int _year;
//    int _month;
//    int _day;
//};
//ostream& operator<<(ostream& out, const Date& d)
//{
//    cout << d._year << '-' << d._month << "-" << d._day;
//    return out;
//}
//
//int main()
//{
//    Date d1(2020, 2, 20);
//    d1 -= 10;
//    Date d2 = d1 + 100;
//    cout << d1 << endl << d2 << endl;
//    cout << d1.operator==(d2) << endl;
//
//    return 0;
//}


#include<string>
class Solution {
public:

    string Add(string& s1, string& s2)
    {
        string ret;
        string::reverse_iterator it1 = s1.rbegin();
        string::reverse_iterator it2 = s2.rbegin();
        int x = 0;
        int y = 0;
        while (it1 != s1.rend() && it2 != s2.rend())
        {
            int a = (*it1 - '0') + (*it2 - '0');
            y = (x + a) % 10;
            x = (x + a) / 10;
            ret.push_back(y + '0');
            ++it2;
            ++it1;
        }
        while (it1 != s1.rend())
        {
            int a = *it1 - '0';
            y = (x + a) % 10;
            x = (x + a) / 10;

            ret.push_back(y + '0');
            ++it1;
        }
        while (it2 != s2.rend())
        {
            int a = *it2 - '0';
            y = (x + a) % 10;
            x = (x + a) / 10;

            ret.push_back(y + '0');
            ++it2;
        }
        if (x)
            ret.push_back(x + '0');
        reverse(ret.begin(), ret.end());

        return ret;
    }

    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0")
            return "0";
        string ret;
        string::reverse_iterator it1 = num1.rbegin();       
        while (it1 != num1.rend())
        {
            string tmp;
            string::reverse_iterator count = num1.rbegin();
            while (count != it1)
            {
                tmp.push_back('0');
                ++count;
            }
            string::reverse_iterator it2 = num2.rbegin();
            int x = 0;
            int y = 0;
            while (it2 != num2.rend())
            {               
                int a = (*it1 - '0') * (*it2 - '0');       
                y = (x + a) % 10;   
                x = (x + a) / 10;
                tmp.push_back(y + '0');
                ++it2;
            }
            if (x)
            {
                tmp.push_back(x + '0');
            }
            reverse(tmp.begin(), tmp.end());

            ret = Add(ret, tmp);
            ++it1;
        }
        return ret;
    }
};
int main()
{
    string s = Solution().multiply("123", "456");
    return 0;
}

